#include <stdio.h>

#define M 128
#define N 32

int m = 0, n = 0;
int c[N][M] = {0};
int w[N] = {0};
int v[N] = {0};

void npack() {
    int i, j;
    for (j=1; j <= m; j++) {
        for (i=1; i <= n; i++) {
            if (j < w[i]) {
                c[i][j] = c[i-1][j];
                continue;
            }
            else if(c[i-1][j-w[i]] + v[i] > c[i-1][j]) {
                c[i][j] = c[i-1][j-w[i]] + v[i];
            }
            else {
                c[i][j] = c[i-1][j];
            }
        }
    }
}

int main() {
    int i, j;
    // input
    scanf("%d %d", &m, &n);
    for (i = 1; i <= n; i++) {
        scanf("%d %d", &w[i], &v[i]);
    }
    npack();
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            printf("%4d ", c[i][j]);
        }
        printf("\n");
    }
    return 0;
}

